      1  /**

      2     A binary tree in which each node has two children.

      3  */

      4  public class BinaryTree

      5  {

      6     private Node root;

      7

      8     /**

      9        Constructs an empty tree.

     10     */

     11     public BinaryTree() { root = null; }

     12

     13     /**

     14        Constructs a tree with one node and no children.

     15        @param rootData the data for the root

     16     */

     17     public BinaryTree(Object rootData)

     18     {

     19        root = new Node();

     20        root.data = rootData;

     21        root.left = null;

     22        root.right = null;

     23     }

     24

     25     /**

     26        Constructs a binary tree.

     27        @param rootData the data for the root

     28        @param left the left subtree

     29        @param right the right subtree

     30     */

     31     public BinaryTree(Object rootData, BinaryTree left, BinaryTree right)

     32     {

     33        root = new Node();

     34        root.data = rootData;

     35        root.left = left.root;

     36        root.right = right.root;

     37     }

     38

     39     class Node

     40     {

     41        public Object data;

     42        public Node left;

     43        public Node right;

     44     }

     45

     46     /**

     47        Returns the height of the subtree whose root is the given node.

     48        @param n a node or null

     49        @return the height of the subtree, or 0 if n is null

     50     */

     51     private static int height(Node n)

     52     {

     53        if (n == null) { return 0; }

     54        else { return 1 + Math.max(height(n.left), height(n.right)); }

     55     }

     56

     57     /**

     58        Returns the height of this tree.

     59        @return the height

     60     */

     61     public int height() { return height(root); }

     62

     63     /**

     64        Checks whether this tree is empty.

     65        @return true if this tree is empty

     66     */

     67     public boolean isEmpty() { return root == null; }

     68

     69     /**

     70        Gets the data at the root of this tree.

     71        @return the root data

     72     */

     73     public Object data() { return root.data; }

     74

     75     /**

     76        Gets the left subtree of this tree.

     77        @return the left child of the root

     78     */

     79     public BinaryTree left()

     80     {

     81        BinaryTree result = new BinaryTree();

     82        result.root = root.left;

     83        return result;

     84     }

     85

     86     /**

     87        Gets the right subtree of this tree.

     88        @return the right child of the root

     89     */

     90     public BinaryTree right()

     91     {

     92        BinaryTree result = new BinaryTree();

     93        result.root = root.right;

     94        return result;

     95     }

     96  }